package union_find_Algorithm;

/**
 * 采用压缩路径法优化并查集算法
 */
@SuppressWarnings("all")
public class UnionFind_compress_path {
    private int maxsize;
    private int[] root;

    public UnionFind_compress_path(int maxsize) {
        this.maxsize = maxsize;
        root = new int[this.maxsize];
        for (int i = 0; i < this.maxsize; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]); // 将最终的根节点直接赋值给x即可
    }

    public void union(int x,int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }

    public static void main(String[] args) {
        UnionFind_compress_path unionFind = new UnionFind_compress_path(6);
        unionFind.union(1,2);
        unionFind.union(3,4);
        unionFind.union(1,4);
        System.out.println(unionFind.find(0));
        System.out.println(unionFind.find(1));
        System.out.println(unionFind.find(2));
        System.out.println(unionFind.find(4));
    }
}
